The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of elements including links (communication paths such as telephone or optical lines) and nodes (for example, routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
One routing protocol used, for example, in the internet is Border Gateway Protocol (BGP). BGP is used to route data between routing domains such as autonomous systems (AS) comprising networks under a common administrator and sharing a common routing policy. BGP routers exchange full routing information during a connection session for example using Transmission Control Protocol (TCP) allowing inter-autonomous system routing. The information exchanged includes various attributes including a next-hop attribute. For example where a BGP router advertises a connection to a network, for example in the form of an IP address prefix, the next-hop attribute comprises the IP address used to reach the BGP router.
Edge or border BGP routers (ASBRs) in a first AS communicate with eBGP peers in a second AS via exterior BGP (eBGP). In addition BGP routers within an AS exchange reachability information using interior BGP (iBGP). As a very large number of routes may be advertised in this manner an additional network component comprising a route reflector is commonly provided which sets up a session with each BGP router and distributes reachability information to each other BGP router.
The border routers in respective AS's can advertise to one another, using eBGP, the prefixes (network destinations) reachable from them, the advertisements carrying information such as AS-path, indicating the AS's through which the route advertisement has passed including the AS in which the advertising border router itself is located, and a BGP Community attribute indicating the manner in which the advertisement is to be propagated. For example if an eBGP advertisement is received with Community attribute No-Advertise, then the border router receiving the advertisement does not advertise the route information to any of its peers, including other routers in its AS. When the routes are advertised internally, additional information such as a local preference and a nexthop field are included. The local preference attribute sets a preference value to use of that particular route for example for a given set of prefixes such that where more than one route is available to other border routers in the AS they will select the route with the highest local preference. The next-hop attribute provides the IP address used for the link between the border router in the AS and its eBGP peer.
Based on the eBGP information received, an ASBR selects its path to another AS. This is done either by forwarding packets for a prefix towards a peer in an adjacent AS which advertised the prefix via eBGP as reachable, to another ASBR in the same AS which advertised the prefix via IBGP as reachable or if appropriate to a router without the AS to which the prefix is attached. Based on the eBGP information received for each prefix from ASBRs in adjacent ASs, an ASBR selects its path for those packets by choosing the ASBR with the “best” path. As reachability is passed from AS to AS, information is added to express the list of ASs that the packet to that prefix would pass through to reach its destination. Accordingly, BGP belongs to the family of routing vector protocols, the path being constructed back via the chain of propagation of the advertised prefix.
To reduce the amount of IBGP messages further, route reflectors may only advertise the best path for a given destination to all border routers in an AS. Accordingly all border routers will forward traffic for a given destination to the border router identified in the best path advertisement. Forwarding of packets within the AS may then simply use Interior Gateway Protocol (IGP) as described in more detail below where the IGP forwarding table will ensure that packets destined for the eventual destination will be forwarded within the AS towards the appropriate border router. Alternatively an ingress border router receiving incoming packets may tunnel the packets to the appropriate egress border router, that is, encapsulate the packets to a destination egress border router for transit across the AS for example using IP or MPLS tunnels. The packets are then decapsulated at the egress border router and forwarded according to the packet destination header.
Within each AS the routing protocol typically comprises an interior gateway protocol (IGP) for example a link state protocol such as open shortest path first (OSPF) or intermediate system-intermediate system (IS-IS).
It is important to minimize packet loss in the case of network component failure. For example an inter domain (eBGP) failure may occur in the case of failure of an inter-AS connection between respective components in first and second ASs of a data communications network. Solutions are described in co-pending patent application Ser. Nos. 11/254,469, filed Oct. 20, 2005; 11/254,609, filed Oct. 20, 2005; and 11/254,589, filed Oct. 20, 2005, the entire contents of which are incorporated by reference for all purposes as if fully set forth herein. According to those approaches, a connection between ASBRs can be repaired if there is an inter-AS link between a second pair of ASBRs between the ASs under consideration. However, the approach is described therein to not support repair in the general case where there is any alternate path between a pair of adjacent ASs including indirect paths via additional ASs.